﻿#define _CRT_SECURE_NO_WARNINGS 1
//已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
//若旋转 4 次，则可以得到[4, 5, 6, 7, 0, 1, 2]
//若旋转 7 次，则可以得到[0, 1, 2, 4, 5, 6, 7]
//注意，数组[a[0], a[1], a[2], ..., a[n - 1]] 旋转一次 的结果为数组[a[n - 1], a[0], a[1], a[2], ..., a[n - 2]] 。
//给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
//你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

//eg:输入：nums = [3, 4, 5, 1, 2]输出：1
//解释：原数组为[1, 2, 3, 4, 5] ，旋转 3 次得到输入数组。

#include <iostream>
using namespace std;

int findMin1(int* nums, int n)
{
	int left = 0, right = n - 1;
	int x = nums[right];
	// 标记⼀下最后⼀个位置的值
	while (left < right)
	{
		int mid = left + (right - left) / 2;
		if (nums[mid] > x) left = mid + 1;
		else right = mid;
	}
	return nums[left];
}

int findMin2(int* nums, int n)
{
	int left = 0, right = n - 1;
	int mid = 0;
	int x = nums[left];
	while (left < right)
	{
		mid = left + (right - left) / 2;
		if (nums[mid] >= x)//注意[2,1]的情况
			left = mid + 1;
		else
			right = mid;
	}
	return nums[left] < x ? nums[left] : x;//注意完全递增的情况
}

int main()
{
	int nums[] = { 4, 5, 6, 7, 0, 1, 2 };
	int target = 0;
	int n = sizeof(nums) / sizeof(nums[0]);
	for (size_t i = 0; i < n; i++)
	{
		cout << nums[i] << ' ';
	}
	cout << endl;

	int an=findMin2(nums, n);
	cout << an<<endl;

	return 0;
}